#include <bits/stdc++.h>

using namespace std;

using ll = long long;

template <ll P>
ll fpow(ll a, ll b)
{
    ll res = 1;
    for (; b; b >>= 1, a = (a * a) % P)
        if (b & 1)
            res = (res * a) % P;
    return res;
}

/**
 * @brief NTT 计算器
 *
 * @tparam G 原根
 * @tparam P 素数
 */
template <ll G, ll P>
struct NTT
{
    int _n;
    int E;
    vector<int> rev;

    /**
     * @brief 构建一个 NTT 计算器
     *
     * @param n 多项式最高项数
     */
    NTT(int n)
    {
        _n = 1;
        E = 0;
        while (_n < n)
        {
            _n <<= 1;
            E++;
        }
        rev.resize(_n);
        // 逆位置对换
        for (int i = 1; i < _n; i++)
        {
            rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (E - 1));
        }
    }

    void _rNTT(ll A[], ll k)
    {
        for (int i = 0; i < _n; i++)
            if (i < rev[i])
                swap(A[i], A[rev[i]]);

        for (int e = 1; e <= E; e++)
        {
            int m = 1 << e;
            ll gn = fpow<P>(fpow<P>(G, (P - 1) / m), k);
            for (int i = 0; i < _n; i += m)
            {
                int hf = m / 2;
                ll g = 1;
                for (int j = 0; j < hf; j++)
                {
                    ll x = A[i + j];
                    ll y = (A[i + j + hf] * g) % P;
                    A[i + j] = (x + y) % P;
                    A[i + j + hf] = (x - y) % P;
                    g = (g * gn) % P;
                }
            }
        }
    }

    /**
     * @brief NTT 过程
     *
     * @param A 系数数组
     */
    void doNTT(ll A[])
    {
        _rNTT(A, 1);
    }

    /**
     * @brief NTT 逆过程
     *
     * @param A 点值数组
     */
    void doINTT(ll A[])
    {
        ll ni = fpow<P>(_n, P - 2);
        _rNTT(A, P - 2);
        for (int i = 0; i < _n; i++)
        {
            A[i] = (A[i] * ni) % P;
            A[i] = (A[i] + P) % P;
        }
    }
};